import java.util.*;

public class Offer37 {
    String treeStr = null;
    int cur = 0;
    int length = 0;

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder builder = new StringBuilder();
        Stack<TreeNode> stack = new Stack<> ();
        // 前序遍历
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                builder.append(root.val);
                builder.append('.');// 隔开每个结点的值
                root = root.left;
            }
            builder.append('n');
            builder.append('.');
            root = stack.pop();
            root = root.right;
        }
        builder.append('n');// 这里调试发现需要补充个空标志n

        return builder.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        this.treeStr = data;
        length = treeStr.length();
        return dfs(treeStr);
    }

    private TreeNode dfs(String treeStr) {
        if (cur < length && treeStr.charAt(cur) == 'n') {
            cur += 2;
            return null;
        }
        TreeNode root = new TreeNode(getValue(treeStr));
        root.left = dfs(treeStr);
        root.right = dfs(treeStr);
        return root;
    }

    private int getValue(String treeStr) {
        int offset = cur;
        while (cur < length && treeStr.charAt(cur) != '.') {
            cur++;
        }
        return Integer.valueOf(treeStr.substring(offset, cur++));// 跳过'.'
    }
}
